Currently there are no efficient methods to represent logic circuit design with Exclusive-OR, (EXOR) terms, Exclusive-NOR (EXNOR) terms, terms with embedded functions, such as f(ABC)=ABC+ABC, and hence there are no efficient techniques available that would extract common terms, or partial functions, and minimize them. One of the reasons for this is that the existing minimization techniques are geared towards extracting prime implicants, also known as AND terms, rather than extracting partial functions, such as ABC+ABC and so on, which would result in achieving better minimization algorithms. The existing minimization algorithms can be divided into two broad categories, namely, those that generate either a sum of products (SOP), or a product of sums (POS), and those that generate EXOR sum of products (ESOP). Therefore, logic circuit designs are restricted to NAND-NAND or NOR-NOR or AND-EXOR structures, even though a better structure could be obtained by using OR, AND, EXOR, EXNOR gates, and other logic structures. Recent PLA, PLD, and FPGA architectures have included explicit EXOR gates which are often left unused when the minimization CAD tools cannot effectively extract the EXOR/EXNOR functions. FPGA's allow us to implement Boolean functions efficiently if they can be represented properly and minimized efficiently by extracting partial functions.
Another problem in the traditional minimization technique is they cannot effectively extract complementary functions in the minimization process. For example, consider a function f(ABCD) that can be represented as: EQU Ag(BC)D+Ag(BC)D
where g(BC)=BC+BC and g=BC+BC. If we can extract BC+BC and BC+BC as complements of each other, then f(ABCD) can be represented more simply as: EQU A(gD+gD)=A(g.sym.D)
The reason is that most minimization techniques try to eliminate one variable at a time, such as ABC+ABC=AB, rather than considering several variables at a time, namely, ABC+ABC. Since the single variable minimization methods use bit manipulation techniques, where each variable is represented by a bit, they do not produce efficient results. For example, the logic function: EQU f(ABCDE)=ABCDE+ABCDE+ABCDE+ABCDE+ABCDE+ABCDE
can be reduced to a very simple structure, A(B.sym.g), where g=CDE+CDE. Unfortunately, prior art minimization methods cannot extract functions like g and still provide the above minimal representation for f(ABCDE). Graph based methods, such as Binary Decision Diagrams (BDD), for Boolean function manipulation try to overcome some of the above problems, however the effectiveness of the result depends on the ordering of the variables.
Due to the shortcomings, drawbacks and limitations of prior art minimization procedures, there has been a long-felt need for new minimization techniques which successfully extract EXOR functions embedded within Boolean expressions. Comparison of new minimization techniques provided by the present invention with traditional SOP minimization CAD tools such as Espresso and McBoole demonstrate that more efficient circuits in terms of the number of logic gates and in terms of size, where the number of gate inputs gives a more accurate size comparison as related to ASIC implementations, can be achieved. A minimization technique in accordance with the present invention that successfully extracts EXOR functions can be very useful in the synthesis of VLSI systems, Built-In Self-Test (BIST) approaches in ASICs, and in the mapping of Boolean expressions into input-limited PLD macrocells and FPGA Look-up Tables while making use of EXOR gates available in the programmable logic blocks but residing external to the macrocells or Look-up Tables themselves, and in minimizing ISCAS85 benchmark circuits for the evaluation of the actual savings in the number of gates. The present invention answers the long-felt need for this capability by providing an identity cell representation that allows the representing of sub-functions as a single entity that can be readily used for minimization in logic circuit design and fabrication.
Prior art approaches, methods and techniques are described in the following publications: Johnson, E. L., et. al "Digital Design: A Pragmatic Approach," PWS Engineering, Boston, Mass., 19**, pp. 39-48;
Damarla, T. and Karpovsky, M., "Fault Detection in Combinational Networks by Reed Muller Transforms," IEEE Trans. Computers, Vol. 38, No. 6, June 1989, pp. 788-797; and
Bryant R. E., "Graph Based Algorithms for Boolean Function Manipulation," IEEE Trans. Computers, Vol C-35, No. 8, August 1986, pp. 509-516.